// 生成距离矩阵和路线矩阵
function getAllPointsDistanceMatrix() {
	// 生成初始矩阵
	distanceMatrix = initialMatrix();
	//	// 生成父点矩阵
	parentMatrix = initialPMatrix(distanceMatrix);
	//	// 生成距离矩阵
	floyd_warshall(distanceMatrix, parentMatrix);
}

function initialMatrix() {
	var result = new Array(inflectionPoint.length);
	for(let i = 0; i < result.length; i++) {
		result[i] = new Array(inflectionPoint.length);
		for(let j = 0; j < result[i].length; j++) {
			result[i][j] = MAX_NUM;
		}
	}
	for(let i = 0; i < inflectionPoint.length; i++) {
		var p1 = inflectionPoint[i];
		var count = inflectionPoint[i].nearPoint.length;
		for(let j = 0; j < count; j++) {
			var p2 = inflectionPoint[inflectionPoint[i].nearPoint[j] - 1];
			var temp = Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
			temp = temp.toFixed(2);
			result[i][inflectionPoint[i].nearPoint[j] - 1] = temp;
		}
		result[i][i] = 0;
	}
	return result;
}

function initialPMatrix(matrix) {
	var result = new Array(matrix.length);
	for(let i = 0; i < result.length; ++i) {
		result[i] = new Array(matrix.length);
		for(let j = 0; j < result[i].length; ++j) {
			if(i == j) {
				result[i][j] = 0;
			} else {
				if(matrix[i][j] != MAX_NUM) {
					result[i][j] = i;
				} else {
					result[i][j] = -1;
				}
			}
		}
	}
	return result;
}

function floyd_warshall(matrix, parent) {
	for(let k = 0; k < matrix.length; ++k) {
		var newMatrix = create2DArray(matrix);
		var newParent = create2DArray(matrix);
		for(let i = 0; i < matrix.length; ++i) {
			for(let j = 0; j < matrix.length; ++j) {
				if(matrix[i][k] * 1 + matrix[k][j] * 1 < matrix[i][j]) {
					newMatrix[i][j] = matrix[i][k] * 1 + matrix[k][j] * 1;
					newParent[i][j] = parent[k][j];
				} else {
					newMatrix[i][j] = matrix[i][j];
					newParent[i][j] = parent[i][j];
				}
			}
		}
		matrix = newMatrix;
		for(let m = 0; m < parent.length; ++m) {
			for(let n = 0; n < parent.length; ++n) {
				parent[m][n] = newParent[m][n];
			}
		}
	}
	distanceMatrix = change2DArray(matrix);
	parentMatrix = parent;
}

function change2DArray(matrix) {
	for(let i = 0; i < matrix.length; i++) {
		for(let j = 0; j < matrix[i].length; j++) {
			matrix[i][j] *= 1;
			matrix[i][j] = matrix[i][j].toFixed(2);
			matrix[i][j] *= 1;
		}
	}
	return matrix;
}

function create2DArray(matrix) {
	var result = new Array(matrix.length);
	for(let i = 0; i < result.length; i++) {
		result[i] = new Array(matrix.length);
	}
	return result;
}